package 中等.树;

/**
 * 给你两个 正整数 数组 arr1 和 arr2 。
 * 正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。
 * 设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554
 * 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。
 * 你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。
 * 返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。
 *
 * @ https://leetcode.cn/problems/find-the-length-of-the-longest-common-prefix/description/
 * @date 2024/02/18
 */
public class 最长公共前缀的长度 {

    public static void main(String[] args) {

    }

    /**
     * 字典树
     * 先将 arr1 放入字典树，然后 arr2 去找最长公共前缀
     */
    public int longestCommonPrefix(int[] arr1, int[] arr2) {

        Trie trie = new Trie();

        for (int num : arr1) {
            trie.add(String.valueOf(num));
        }
        int ans = 0;
        for (int num : arr2) {
            int curLen = trie.findMaxPrefix(String.valueOf(num));
            ans = Math.max(ans, curLen);
        }

        return ans;
    }

    public class Trie {

        private Trie[] chirdren = new Trie[10];

        private void add(String str) {
            Trie cur = this;

            for (char c : str.toCharArray()) {
                if (cur.chirdren[c - '0'] == null) {
                    cur.chirdren[c - '0'] = new Trie();
                }
                cur = cur.chirdren[c - '0'];
            }
        }

        private int findMaxPrefix(String str) {
            int len = 0;
            Trie cur = this;
            for (char c : str.toCharArray()) {
                if (cur.chirdren[c - '0'] != null) {
                    len++;
                    cur = cur.chirdren[c - '0'];
                } else {
                    break;
                }
            }
            return len;
        }

    }

}
